Australian Provisional Patent Application No. PQ6911, Apr. 14, 2000 (claiming priority)
U.S. Pat. No. 5,579,455, November 1996, Greene
U.S. Pat. No. 5,613,050, March 1997, Hochmuth
U.S. Pat. No. 5,751,291, May 1998, Olsen
U.S. Pat. No. 5,914,721, June 1999, Lim
U.S. Pat. No. 5,949,423, September 1999, Olsen
U.S. Pat. No. 6,172,679, January 2001, Lim
Airey, J. M., Increasing update rates in the building walkthrough system with automatic model-space subdivision and potentially visible set calculations. PhD Thesis, University of North Carolina 1990.
Durand, F., G. Drettakis, J Thollot and C. Pucch, Conservative visibility preprocessing using extended projections Siggraph 2000.
Greene, N, Hierarchical z-buffer visibility, Siggraphxe2x80x9493 conference, 1993
Greene, N., Hierarchical rendering of complex environments, PhD dissertation, University of California, Santa Cruz 1995.
Hornung, C., A method for solving the visibility problem, EEE Computer Graphics and Applications, vol. 4, 1984.
Koltun, V., Y. Chrysanthou and D. Cohen-Or, Virtual Occluders: An Efficient Intermediate PVS representation, EGRW""2000.
Lim, H. L., Rendering techniques in three-dimensional computer graphics, Ph.D. thesis, University of Sydney, 1993.
Schaufler, G., J. Dorsey, X. Decoret, and F. X. Sillion, Conservative Volumetric Visibility with Occluder Fusion, Siggraph 2000.
Teller S., Visibility Preprocessing for Interactive Walkthrough, Siggraph""91.
Teller, S., Visibility computations in densely occluded polyhedral environment, PhD. thesis, University of California at Berkeley, 1992.
Wonka P., D. Schmalstieg, Occluder Shadows for Fast Walkthroughs of Urban Environments, Eurographics""99.
Wonka, P., Michael Wimmer, Dieter Schmalstieg, Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs, EGRWS 2000.
Not Applicable
Not Applicable
1. Field of Invention
The present invention relates to computer graphics and, in particular, to the efficient determination of visible and/or invisible surfaces to thereby preferably permit improved visibility or visibility-related computations, generally in 3D systems.
2. Description of the Prior Art
In 3D computer graphics, the determination of the visibility of surfaces is known as hidden surface removal and is performed by the hidden surface algorithms. The most common hidden surface algorithm has been the z-buffer algorithm. However, the traditional hidden surface removal approach is incapable of treating visible and invisible surfaces differently. They have to accord the same importance to all these surfaces and treat them in equal detail to determine their visibility. To address this limitation, a new generation of techniques known as the occlusion culling methods have been created. These methods apply various strategies to quickly decide whether some surfaces are hidden by the other surfaces (the occluders). The present invention is based heavily and borrows many terminologies from the earlier references by Airey, Teller and the inventor of this application
It is an object of the present invention to substantially overcome or ameliorate the problems associated with the prior art, through provision of improved methods for performing visibility calculations.
In accordance with one aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are visible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, further comprising the step of determining surfaces or their sub-elements that are visible, wherein only the remaining surfaces or their sub-elements are excluded from said hidden surface computations.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations. Said method further comprises the step of storing in computer storage information for said hidden surfaces, and the step of subsequently accessing said stored information for said hidden surface computations.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations. Said method comprises the steps of determining the penumbra regions, and checking, for each surface whose visibility is to be determined, whether the projection of said surface falls within on said penumbra regions.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements for said hidden surface computations. Said method further comprises the steps of combining the fuzzy projections, and the determination of the relationship between the combined fuzzy projections with the projections of surfaces whose visibility are to be determined.
In accordance with another aspect of the invention, there is disclosed a method of detecting before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations. Said method further comprises the steps of computing the probabilities of areas on the fuzzy projection planes or the combined fuzzy projection planes; and determining whether said areas are fully occluded based on the probabilities computed.